Trong lý thuyết độ phức tạp tính toán, NP là viết tắt của "nondeterministic polynomial time" (thuật toán bất định trong thời gian đa thức). Cụ thể hơn, NP là tập hợp các bài toán quyết định giải được trong thời gian đa thức bởi máy Turing bất định. Một định nghĩa khác của NP là tập hợp các bài toán quyết định mà trong trường hợp câu trả lời là "có", tồn tại một chứng minh có độ dài đa thức có thể kiểm chứng được trong thời gian đa thức bởi máy Turing tất định.